package com.jiazhong.basic.pack0315.demo.shousi;


public class LinkedListDemo<E> implements ListDemo<E> {

    private int size = 0;
    private Node<E> first;
    private Node<E> last;

    @Override
    public void add(E e) {
        // 产生对象
        Node newNode = new Node(null, e, null);
        // 上一个人
        Node l = last;
        // l==null 代表集合没有元素
        if (l == null) {
            first = newNode;
        } else {
            // 设置两者的关系
            newNode.prev = l;
            l.next = newNode;
        }
        last = newNode;
        size++;
    }

    @Override
    public void add(int index, E e) {

        if (index == size) {
            add(e);
            return;
        }
        Node node = node(index);
        Node newNode = new Node(null, e, node);
        if (node == first) {
            first = newNode;
        } else {
            newNode.prev = node.prev;
            node.prev.next = newNode;
        }
        node.prev = newNode;
        size++;
    }

    @Override
    public E get(int index) {
        return (E) node(index).item;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("越界了");
        }
        if (index == 0) {
            first = first.next;
            first.prev = null;
        } else if (index == size - 1) {
            last = last.prev;
            last.next = null;
        } else {
            Node node = node(index);
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }

        size--;
    }

    private Node node(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("越界了");
        }
        if (index < (size >> 1)) {
            Node node = first;
            for (int i = 0; i < size; i++) {
                if (i == index) {
                    return node;
                }
                node = node.next;
            }
        } else {
            Node node = last;
            for (int i = size - 1; i > -1; i--) {
                if (i == index) {
                    return node;
                }
                node = node.prev;
            }
        }
        return null;
    }

    @Override
    public String toString() {
        String str = "[";
        Node node = first;
        while (true) {
            str += node.item + ",";
            node = node.next;
            if (node == null) {
                break;
            }
        }
        str += "]";
        return str;
    }

    private class Node<E> {
        private E item; // 保存的内容
        private Node<E> prev;
        private Node<E> next;

        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
}
